package sort;

public class SortTest {

	public static void main(String[] args) throws InstantiationException, IllegalAccessException {
		int randomArr[] = createRandomArr(100000);
		ISort[] sortAlgorithm = 
			{BubbleSort.class.newInstance(),
			CountSort.class.newInstance(),
			HeapSort.class.newInstance(),
			InsertSort.class.newInstance(),
			MergeSort.class.newInstance(),
			QuickSort.class.newInstance(),
			RadixSort.class.newInstance(),
			SelectSort.class.newInstance(),
			ShellSort.class.newInstance()};
		for (int i = 0; i < sortAlgorithm.length; i++) {
			int[] tmpArr = randomArr.clone();
			long start = System.currentTimeMillis();
			sortAlgorithm[i].sort(tmpArr);
			long end = System.currentTimeMillis();
			System.out.print(sortAlgorithm[i].getClass().getName() + ":" + (end - start) + "ms ");
			if(checkArrOrder(tmpArr)) {
				System.out.println("PASS");
			}else {
				System.out.println("Error");
			}
		}
	}

	/**
	 * 产生不重复的随机数
	 * 
	 * @param cnt 个数
	 * @return
	 */
	public static int[] createRandomArr(int cnt) {
		int[] ret = new int[cnt];
		for (int i = 0; i < cnt; i++) {
			ret[i] = i + 1;
		}
		for (int i = 0; i < cnt; i++) {
			int randomVal = (int) (Math.random() * cnt);
			swap(ret, i, randomVal);
		}
		return ret;
	}

	/**
	 * 交换数组两个元素
	 * 
	 * @param arr
	 * @param index1
	 * @param index2
	 */
	public static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}

	/**
	 * 检查数组顺序是否递增
	 * 
	 * @param arr
	 * @return
	 */
	public static boolean checkArrOrder(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			if (arr[i] > arr[i + 1]) {
				return false;
			}
		}
		return true;
	}
}
